package com.mlh.linkedlist;

//给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
public class 两两交换链表中的节点 {
	public ListNode method1(ListNode head) {
		//奇数 留一个不换
		//偶数 全换
		//0 个节点  1个节点
		if(head==null||head.next==null){
			return head;
		}
		ListNode pre=new ListNode();
		ListNode newHead=head.next;
		pre.next=head;
		//pre 0  1  2  保持1  让0指向2  1插入到0前面
		//边界条件也很好处理
		while (pre.next!=null&&pre.next.next!=null){
			ListNode temp=pre.next.next;
			pre.next.next=temp.next;
			temp.next=pre.next;
			pre.next=temp;
			pre=pre.next.next;
		}
		return newHead;
	}
	public ListNode practice(ListNode head) {
		if(head==null||head.next==null){
			return head;
		}
		//用一个哨兵节点就很好解决
		ListNode pre=new ListNode();
		pre.next=head;
		head=head.next;
		ListNode temp=null;
		while (pre.next!=null&&pre.next.next!=null){
			temp=pre.next.next;
			pre.next.next=pre.next.next.next;
			temp.next=pre.next;
			pre.next=temp;
			pre=pre.next.next;
		}
		return head;
	}

	public ListNode practice2(ListNode head) {
		ListNode pre=new ListNode(),sentry=pre;//设置一个哨兵节点 以及交换节点的前一个节点  很好解决该题目
		//设置好这两个节点 模拟一下交换过程就写出来了
		pre.next=head;
		while(pre.next!=null&&pre.next.next!=null){
			ListNode temp=pre.next.next;
			pre.next.next=temp.next;
			temp.next=pre.next;
			pre.next=temp;
			pre=pre.next.next;
		}
		return sentry.next;
	}
}
